package com.ahpu.lyf.stack;

import java.util.ArrayList;
import java.util.Stack;

public class Calculator {
    public static void main(String[] args) {
        String exp="5+(11+4)*4-2";
        ReversePolishCalculator calculator=new ReversePolishCalculator();
        System.out.println(exp+" = "+calculator.calculate(exp));
    }
}

class ReversePolishCalculator{
    /**
     * 对外提供的计算方法
     * @param exp 要计算的中缀表达式
     * @return 计算结果
     */
    public int calculate(String exp){
        return calculateSuffixExp(parseSuffixExpList(toInfixExpList(exp)));
    }

    /**
     * 将中缀表达书拆分放到list
     * @param exp 中缀表达式
     */
    private ArrayList<String> toInfixExpList(String exp){
        ArrayList<String> expList=new ArrayList<>();
        //字符串索引
        int index=0;
        int length = exp.length();
        StringBuilder str;
        //索引未越界
        while (index<length){
            //拿到字符串指定索引处的字符
            char charAt = exp.charAt(index);
            //如果是非数字则直接放到list
            if (charAt<'0'||charAt>'9') {
                expList.add(String.valueOf(charAt));
                //索引后移
                index++;
            }
            //是数字需要考虑多位数
            else {
                //初始化一个字符串用于合成多位数
                str = new StringBuilder();
                //索引未越界且是数字
                while (index<length&&exp.charAt(index)>='0'&&exp.charAt(index)<='9'){
                    //追加到字符串
                    str.append(exp.charAt(index));
                    //索引后移
                    index++;
                }
                //当循环跳出说明索引越界了或者遇到了非数字，则多位数已经拼接完成，追加到list
                expList.add(str.toString());
            }
        }
//        System.out.println(expList);
        return expList;
    }

    /**
     * 获取运算符优先级的
     * @param operation 操作符
     * @return 运算符优先级
     */
    private int getOpeValue(String operation){
        int res=0;
        switch (operation){
            //定义+-优先级为0
            case "+":
            case "-":
                 break;
            //定义*/优先级为1
            case "*":
            case "/":
                res= 1;
                break;
            default:
                System.out.println("不存在操作符");
                break;
        }
        return res;
    }

    /**
     * 中缀表达式转换为逆波兰表达式
     * @param expList 中缀表达式的list
     * @return 逆波兰表达式的list
     */
    private ArrayList<String> parseSuffixExpList(ArrayList<String> expList){
        //初始化两个栈
        Stack<String> s1=new Stack<>(); //符号栈
        //说明:因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
        //因此比较麻烦，这里我们就不用Stack<String〉直接使用List<String> s2
        //Stack<String> s2 = new Stack<String>();   //储存中间结果的栈s2
        ArrayList<String> s2=new ArrayList<>();
        //从左到右扫描中缀表达式
        expList.forEach(s->{
            //遇到操作数时压入s2,正则匹配纯数字
            if (s.matches("\\d+")){
                s2.add(s);
            }
//            遇到括号时:
//            1.如果是左括号“("，则直接压入s1
//            2.如果是右括号“)，则依次弹出s1栈顶的运算符，并压入s2，直到遇到"("为止，此时将这一对括号丢弃
            else if (s.equals("(")){
                s1.push(s);
            }else if (s.equals(")")){
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();
            }
//            遇到运算符时,比较其与s1栈顶运算符的优先级:
//            1.如果s1为空，或栈顶运算符为左括号“("，则直接将此运算符入栈﹔
//            2.否则,若优先级比栈顶运算符的高,也将运算符压入s1;
//            3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到第一条与s1中新的栈顶运算符相比较;
            else {
                while (true){
                    if (s1.isEmpty()||s1.peek().equals("(")||getOpeValue(s)>getOpeValue(s1.peek())) {
                        s1.push(s);
                        break;
                    }
                    else {
                        s2.add(s1.pop());
                    }
                }
            }
        });
//        6)重复步骤2至5,直到表达式的最右边
//        7)将s1中剩余的运算符依次弹出并压入s2
        while (!s1.isEmpty())
            s2.add(s1.pop());
//        System.out.println(s2);
        return s2;
    }

    /**
     * 后缀表达式(逆波兰表达式)计算的方法
     * @param suffixExpList 后缀表达式的切割列表
     * @return 计算结果
     */
    private int calculateSuffixExp(ArrayList<String> suffixExpList){
        //初始化一个栈
        Stack<String> stack=new Stack<>();
        //遍历后缀表达式列表
        suffixExpList.forEach(str->{
            //如果是数字直接入栈
            if (str.matches("\\d+"))
                stack.push(str);
            //是操作符则从站内取出次顶元素及栈顶元素进行运算符运算后再入栈
            else {
                Integer num2 = Integer.parseInt(stack.pop());   //栈顶元素
                Integer num1 = Integer.parseInt(stack.pop());   //次顶元素
                switch (str){
                    case "+":
                        stack.push(String.valueOf(num1+num2));break;
                    case "-":
                        stack.push(String.valueOf(num1-num2));break;
                    case "*":
                        stack.push(String.valueOf(num1*num2));break;
                    case "/":
                        stack.push(String.valueOf(num1/num2));break;
                }
            }
        });
        return Integer.parseInt(stack.pop());

    }


}
